package dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author pengfei.hpf
 * @date 2020/2/10
 * @verdion 1.0.0
 * Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies:
 *
 * Si % Sj = 0 or Sj % Si = 0.
 *
 * If there are multiple solutions, return any subset is fine.
 *
 * Example 1:
 *
 * Input: [1,2,3]
 * Output: [1,2] (of course, [1,3] will also be ok)
 * Example 2:
 *
 * Input: [1,2,4,8]
 * Output: [1,2,4,8]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/largest-divisible-subset
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LargestDivisibleSubset {

    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if(nums == null || nums.length == 0){
            return res;
        }
        int[] dp = new int[nums.length];
        int[] rec = new int[nums.length];
        Arrays.sort(nums);
        int max = 0;
        int maxRec = 0;
        for(int i = 0; i < nums.length; i ++){
            int curMax = 0;
            int recSub = i;
            dp[i] = 1;
            rec[i] = i;
            for(int j = i - 1; j >=0; j--){
                if(nums[i] % nums[j] == 0){
                    if(dp[j] > curMax){
                        dp[i] = dp[j] + 1;
                        curMax = dp[j];
                        recSub = j;
                    }
                }
            }
            if(dp[i] > max){
                max = dp[i];
                maxRec = i;
            }
            rec[i] = recSub;
        }

        int i = maxRec;
        while(rec[i] != i){
            res.add(0,nums[i]);
            i = rec[i];
        }
        res.add(0,nums[i]);
        return res;
    }
}
